Paxos

关注的点

选取提案的规则:

如果acceptor通过提案[M, ]的prepare请求,则向proposer保证以下承诺:

  1. acceptor承诺不再通过编号小于等于M的提案的prepare请求
  2. acceptor承诺不再通过编号小于M的提案的accept请求,也就是不再通过编号小于M的提案
  3. 如果acceptor已经通过某一提案,则承诺在prepare请求的响应中返回已经通过的最大编号的提案内容。如果没有通过任何提案,则在prepare请求的响应中返回空值

proposer在发起accept请求时,提案值由prepare响应决定。如果prepare响应有返回已通过的提案值,该accept请求则使用prepare响应中的值。如果prepare响应没有已通过的提案值,则有该proposer任意指定。

ZAB

消息广播模式

消息广播模式是一个类似于二阶段提交(2PC)过程,与2PC不同的是,ZAB移除了第二阶段的中断逻辑。所有的Follower要么接收该Proposal,要么抛弃Leader服务器。这意味着Leader收到过半的Ack响应后就可以提交该事务了,而不需要等待所有的Follower都返回Ack。

  1. 客户端发起事务请求,由Leader进行处理
  2. Leader将该请求转换为事务Proposal,同时为Proposal分配一个全局的ID,即zxid
  3. Leader为每个Follower维护一个FIFO队列,将上一步生成的Proposal放入队列中,进行广播
  4. Follower收到Proposal后,会首先将其以事务日志的方式写入本地磁盘中,写入成功后向Leader反馈一个响应消息
  5. Leader收到过半的Ack响应后,自己完成对该Proposal的提交后,向每个Follower的队列中,写入Commit消息进行广播
  6. Follower接收到Commit消息后,会将上一条事务提交

zxid,用于提交提案的先后顺序。Leader提交提案是有顺序性的,按照zxid的大小,按顺序提交提案,如果前一个提案未提交,此时是不会提交后一个提案的。

崩溃恢复模式

约定:

  1. ZAB需要确保那些已经在Leader上提交的事务最终被所有服务器都提交。
  2. ZAB需要确保丢弃那些仅仅只在Leader上被提出的事务。
Leader选举(ELECTION)

Leader选举PK的规则包含以下几个方面:

  • 任期编号(epoch),优先判断epoch,epoch大的节点当选Leader
  • 事务标示符(zxid),epoch相同,则比较zxid,zxid大的当选Leader
  • 节点ID,epoch、zxid都一致,则比较节点ID(在myid文件中指定的值)
  1. leader宕机,各个follower开始leader选举PK
  2. 各个follower都投票给自己,封装一个选票信息,广播给其他的follower。选票信息包含:
    • 自己所提议的节点ID
    • 自己所提议节点所处leader周期
    • 自己所提议节点拥有最大的zxid
    • 投票节点标示
  3. 其他节点收到选票信息后,根据上述规则开始和自己所提议的节点进行PK。如果选票有更新,当前节点则继续广播自己更新之后的选票信息
  4. 最后各节点的选票池,都有过半的选票支持某一节点,该节点晋升为准leader,完成选举
  5. 各节点分别修改自己的状态,准leader修改为LEADING,其余修改为FOLLOWING
发现(DISCOVERY)

该阶段用于确立Leader的领导关系,由Follower会主动联系准Leader。

  1. Follower将自己最后接受的事务Proposal的epoch值发送给准Leader,记作FOLLOWERINFO。
  2. 准Leader收到来自过半(包含B节点自己)的FOLLOWERINFO消息后,选取最大的epoch值,对其进行加1,作为新的epoch值,并封装成LEADERINFO消息发给这些过半的Follower。
  3. Follower收到LEADERINFO消息后
    • 更新自己的epoch
    • 将自己的运行状态变更为SYNCHRONIZATION
    • 返回ACKEPOCH给准Leader。
  4. 准Leader收到过半的ACKEPOCH消息后,也将自己的运行状态修改为SYNCHRONIZATION。至此完成发现阶段的工作,集群确立Leader的领导关系。
数据同步(SYNCHRONIZATION)

该阶段是实现崩溃恢复的关键步骤,由Leader发送数据给Follower处理。数据内容分三种:DIFF、TRUNC、SNAP。

  1. Leader根据Follower的最大zxid选择同步方式
  2. Leader将同步方式和需要同步的数据,一起封装为NEWLEADER消息发给Follower
  3. Follower在收到NEWLEADER消息后,进行修复不一致数据,并返回给Leader响应Ack消息
  4. Leader在收到过半Ack消息后,则完成数据同步阶段,将自己运行状态修改为BROADCARST(广播状态),并发送UPTODATE消息给过半的Follower,通知他们完成数据同步,修改运行状态修改为BROADCARST

Raft

leader选举

日志同步